1. Field of the Invention
The present invention generally relates to address translation caching and, more particularly, to determining cache entries for replacement.
2. Description of the Related Art
Computing systems often include central processing units (CPUs) to perform operations relating to the processing of data. The data processed by a processor may include instructions, which are executed by the processor, as well as data which is manipulated by the processor using the instructions. Computing systems also include memory used to store data and instructions for later use.
To provide for faster access to data and instructions, as well as better utilization of the CPU, the CPU may have several caches. A cache is a memory which is typically smaller than the main memory of the computer system and is typically manufactured on the same die (i.e., chip) as the processor. Cache memory typically stores duplications of data from frequently used main memory locations. Caches may also store virtual memory translation information such as segment tables and page tables. These tables aid in the translation of virtual memory addresses to the corresponding physical memory address. When a processor wishes to read from a memory location in main memory, the processor will check the memory cache first to see if a duplication of the main memory location is present in the cache. If so, the processor uses the data in the cache. If the data is present in the cache it is commonly referred to as a “cache hit”. If the data is not present in the cache, then the data must be fetched from main memory. This is commonly referred to as a “cache miss”.
Due to the limited size of cache memory within the processor, data within the cache that has not been used in a relatively long time is replaced with the data fetched from main memory due to a cache miss. This is based on the theory that it is more likely that the fetched data will be requested sooner than the data replaced.
Some CPUs use hardware logic to determine what data within the memory cache is to be replaced. This is commonly referred to as hardware miss handling. Hardware miss handling often uses a combination of a least recently used (LRU) table and lock bits associated with the cache entries to determine which data location or locations to replace with data fetched from main memory.
An LRU table contains information relating to how often different cache entries have been used. More specifically the table may be able to determine which entries are the least recently used entries. The lock bits are bits on each cache entry within the cache that may be set to indicate that the cache entry should not be replaced with data fetched from main memory.
Some CPUs allow software to determine how a miss is handled for address translation. When a miss occurs when software address translation cache miss handing is enabled on the CPU, a cache miss causes an exception. The exception results in an interrupt so that software executing on the CPU can fetch the missing memory and determine where in the address translation cache the data fetched from memory needs to be placed. Software address translation cache miss handling does not use the hardware LRU table to determine where to place fetched data into the cache.
Problems arise in modern CPUs when both hardware and software address translation cache miss handling are enabled at the same time. One problem is which entries to replace when both hardware and software address translation cache miss handling are enabled, and there are locked entries within the cache. For example, if hardware miss handling were enabled and all entries had their lock bits asserted, the hardware would still be able to replace the entity. However, if software address translation cache miss handling was enabled as well, and all entries had their lock bits asserted, the hardware would not replace a cache line entry. Rather, hardware would cause an exception. Another problem is how to update the LRU table when hits occur under software address translation cache miss handling.
Therefore, there exists a need for an improved way to calculate the replacement way within a memory cache that is effective with different combinations of hardware miss handling, software address translation cache miss handling, and lock bits.